Zápočét 13.1.2010

• popsat TS, ktery prijima jazyk $\{1^{2^x},x\ge 0\}$

• odvodit ze $x-1$ je PRF

• pokud mam blackbox ktery resi rozhodovaci SAT (ANO/NE) jak pomoci nej sestrojim algoritmus ktery najde dane ohodnoceni promennych

• dokaz ze celociselne programovani je NP-uplne